package q417_pacificAtlantic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution_1 {
    /*
    先用BFS解决该问题
    首先我们考虑从每个边界向高处拓展的水流
    创建两个boolean矩阵 考虑每个海洋能够拓展到的位置
    通过BFS反复出入栈来标记
    最后观察哪个block同时满足能够流到两个海洋即可
     */
    List<List<Integer>> res = new ArrayList<>();
    int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        boolean[][] pacific = new boolean[heights.length][heights[0].length];
        boolean[][] atlantic = new boolean[heights.length][heights[0].length];
        for (int i = 0; i < heights.length; i++) {
            bfs(i, 0, pacific, heights);
        }
        for (int j = 1; j < heights[0].length; j++) {
            bfs(0, j, pacific, heights);
        }
        for (int i = 0; i < heights.length; i++) {
            bfs(i, heights[0].length - 1, atlantic, heights);
        }
        for (int j = 0; j < heights[0].length - 1; j++) {
            bfs(heights.length - 1, j, atlantic, heights);
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[0].length; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<Integer>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;

    }

    private void bfs(int r, int c, boolean[][] ocean, int[][] heights) {
        if (ocean[r][c]) return;
        ocean[r][c] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] block = queue.poll();
                for (int[] dir : dirs) {
                    int newRow = block[0] + dir[0], newCol = block[1] + dir[1];
                    if (newRow >= 0 && newRow < heights.length && newCol >= 0 && newCol < heights[0].length && heights[newRow][newCol] >= heights[block[0]][block[1]] && !ocean[newRow][newCol]) {
                        ocean[newRow][newCol] = true;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }

            }
        }
    }


}
